package leetcode_周赛._2022._202211;

import general_class.TreeNode;

import java.util.*;

/**
 * 第 319 场周赛
 *
 * @author yezh
 * @data 2022/11/13 11:05
 */
public class _13 {

    public static void main(String[] args) {
        System.out.println(new _13().subarrayLCM(new int[]{13, 2, 14, 9, 13, 1, 11, 1, 8}, 11));
    }

    /**
     * 6234. 最小公倍数为 K 的子数组数目
     * 算法：数学
     * 遍历所有子数组
     * 算出子数组中各个元素的最小公倍数
     * 三个数的最小公倍数, (a, b) 的最小公倍数为 t, (a, b, c) 的最小公倍数为 (t, c) 的最小公倍数
     */
    public int subarrayLCM(int[] nums, int k) {
        int ans = 0, n = nums.length, cnt = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                cnt = lcm(cnt, nums[j]);
                if (cnt == k) ++ans;
                else // 剪枝
                    if (cnt > k) break;
            }
            cnt = 1;
        }
        return ans;
    }

    int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    /**
     * 6235. 逐层排序二叉树所需的最少操作数目
     * 算法：广度优先搜索 + 置换环 + 离散化
     */
    public int minimumOperations(TreeNode root) {
        int ans = 0;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            int[] nums = new int[size];
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                nums[i] = node.val;
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }
            ans += getMinOperations(nums);
        }
        return ans;
    }

    int getMinOperations(int[] nums) {
        int res = 0, len = nums.length;
        Map<Integer, Integer> map = new HashMap<>(len);
        for (int i = 0; i < len; i++) map.put(nums[i], i);
        Arrays.sort(nums);
        // 离散化, [7, 6, 8, 5] == [0, 1, 2, 3]
        // [5, 6, 7, 8] == [3, 1, 0, 2]
        // 离散化之后, 可以找到需要调换位置的一组
        // 找到这一组后, 这一组要调换的次数 = 这一组的长度 - 1
        for (int i = 0; i < len; i++) nums[i] = map.get(nums[i]);
        for (int i = 0; i < len; i++) {
            if (nums[i] == -1) continue;
            int num = nums[i], cnt = 1;
            while (num != i) {
                ++cnt;
                int tmp = nums[num];
                nums[num] = -1;
                num = tmp;
            }
            res += cnt - 1;
        }
        return res;
    }

}
